COMMENT ⊗   VALID 00010 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\init{
C00004 00003	\chapbegin{1}		% Here beginneth Chapter 1
C00005 00004	\sectionbegin[1]{Context}
C00008 00005	\sectionbegin[2]{Task}
C00027 00006	\sectionbegin[3]{Scope of the Problem}
C00032 00007	\sectionbegin[4]{Method}
C00036 00008	\sectionbegin[5]{Range of Application}
C00040 00009	\sectionbegin[6]{A Word about natural language}
C00043 00010	\sectionbegin[7]{Themes}
C00046 ENDMK
C⊗;
\init{
\input cmpdes
\input temacs
\def\draft{T}
\titlepage
\newpage
\setcount0 1
\parttitle{TEIRESIAS: META-LEVEL KNOWLEDGE IN KNOWLEDGE-BASED SYSTEMS}
}
\baselineskip 12pt
\chapbegin{1}		% Here beginneth Chapter 1
\chaptertitle{INTRODUCTION}
\rjustline{\:B Introduction}
\tenpoint
\vskip 13.5pc

\epigraph{I will tell you the whole truth.}
\author{Sophocles}
\source{Oedipus the King, line 800}
\epigraphend
\sectionbegin[1]{Context}
	The creation and management of large knowledge bases has become a
central problem of artificial intelligence (AI) research.  This is a result
of two recent trends: an emphasis on the use of large stores of
domain-specific knowledge as a base for high-performance programs, and a
focus on problems taken from real world settings.  These trends are
motivated by the belief that artificial problems may, in the long run,
prove more of a diversion than a base for development and by the belief
that the field of AI has progressed far enough to provide high performance
systems capable of solving real problems.  Both of these mean an emphasis
on the accumulation and management of large collections of knowledge, and
in many systems embodying these trends (\eg, [MACSYMA74], [Buchanan71],
[Finkel74], [Hart75]), much time has been spent building and
maintaining such knowledge bases.  Yet there has been little discussion or
analysis of the concomitant problems.  We attempt to define here some
of the issues involved and explore the steps taken toward solving a number
of these problems.  We describe a computer program called {\TEIRESIAS}\ffnote{The
program is named for the blind seer in {\sl Oedipus the King}
[Sophocles27], and selected quotes from the play are scattered through the
text.  As will become clear, the program, like the prophet, has a ``higher
order'' of knowledge.  However, this rather thin analogy should not be
pursued too vigorously.  Most of the virtue in having a name for the
program lies in the convenience it offers for reference to a large body of
code.} that has been designed and implemented to deal with some of the
important issues.

\sectionskip
\sectionbegin[2]{Task}
	The fundamental problem discussed in the following chapters is the
creation of a set of tools for the construction, maintenance, and use of
large, domain-specific knowledge bases.

	Two major goals were used as guidelines in creating those tools.
First, it should be  possible for an expert in the domain of application
to ``educate'' the performance program interactively, commenting on and
correcting its behavior.\fnote{``Expert'' is used to mean someone expert in an
applications domain but assumed to be inexperienced in programming.}
Second, it should be possible for the expert to assemble and maintain a
large body of knowledge.

	Concerning the first goal, consider the two alternative approaches shown in 
Figure 1--1.  In the traditional approach, the behavior of the program is
interpreted by an assistant for the benefit of an expert who knows little
or no programming.  The expert's comments on and corrections to program
behavior are in turn interpreted by the assistant who then makes the
appropriate changes to the program.

% ⊂∂∂∂∂∂∂∂∂∂∂⊃         ⊂∂∂∂∂∂∂∂∂∂∂∂∂⊃          ⊂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂⊃
% }  expert  }  ←∂∂∂   } assistant  }   ←∂∂∂   }  performance  }
% }          }  ∂∂∂→   }            }   ∂∂∂→   }    program    }
% α%∂∂∂∂∂∂∂∂∂∂$         α%∂∂∂∂∂∂∂∂∂∂∂∂$          α%∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂$
% 
% .once select 1
% The traditional approach
% 
% 
% ⊂∂∂∂∂∂∂∂∂∂∂⊃               ⊂∂∂∂∂∂∂∂∂∂∂∂∂∂⊃
% }          }  explanation  }             }
% }  expert  }  ←∂∂∂∂∂∂∂∂∂∂  } performance }
% }          }  ∂∂∂∂∂∂∂∂∂∂→  }   program   }
% }          }   knowledge   }             }
% α%∂∂∂∂∂∂∂∂∂∂$   transfer    α%∂∂∂∂∂∂∂∂∂∂∂∂∂$
% 
% .ONCE SELECT 1
% An alternative approach

\vskip 12pc
\figtitle 1-1{Building high-performance programs.}

	The alternative approach puts the expert in more direct
communication with the program, so that he can discover what the program is
doing and why, and can modify it himself to produce the desired behavior.
It is this alternative toward which we have been working.

	In this situation, the interaction between the expert and the
program resem\-bles that of a teacher who continually challenges a student
with new problems to solve and carefully observes the student's
performance.  The teacher may interrupt the student to request a
justification of some particular step taken in attacking the problem or he
may challenge the final result (both of these are information transfer from
{\index{ explanation}}right to left, which we label ``explanation'').
This process may uncover a
fault in the student's knowledge of the subject and result in the transfer
of information to correct it (information flow from left to
right, {\index{ knowledge transfer}}``knowledge transfer'').
{\index{ knowledge acquisition}}
{\index{ knowledge base management}}

	The second goal was to make it possible for the expert
to assemble and maintain a large body
of knowledge.  It is rarely possible to put together a large knowledge
base in one or even a few passes.  The process is, instead, one of constant
trial
and reevaluation, an incremental approach to competence.  When knowledge is
accumulated over a long period of time, the knowledge base undergoes numerous
changes.  If it is to grow very large, making those changes must be a reasonable
task.  From this simple observation comes one major theme of this work: the
{\index{ knowledge representation}}search for knowledge representations
and system designs that offer a high degree
of flexibility in the face of changes.  One way to achieve flexibility is
to build a separate acquisition
program specifically tailored to the structure of the knowledge base.  A more
fundamental solution would involve designing a knowledge base that  is
{\index{ flexibility}}inherently flexible, one that would easily accommodate changes.
Elements of both these approaches will be found in the chapters that follow.

	Not surprisingly, both goals---forging a direct link between
expert and pro\-gram, and assembling large amounts of knowledge---have significant
impacts on the design of the performance program.  In particular, attempting to
achieve both of them simultaneously is predicated on an important
assumption:
that it is possible to distinguish between basic {\sl formalism}{\index{ expertise}}
and {\sl degree of expertise} or, equivalently, that the control structure and
{\index{ knowledge base}}representation can be considered separately from the
knowledge base.\ffnote{Note
that this distinction is not specific to any particular system or knowledge
representation.  As long as it is possible to make this distinction, the general
approach used here will remain valid.}
The basic control structure(s) and representations employed in the performance program
are assumed to be established and debugged, and the fundamental approach to the
problem is assumed acceptable.  The task of the expert, then, is to enlarge the
knowledge base by adding new knowledge to be used in one of the established
ways.  In other words, we are assuming that {\sl how} the knowledge is
to be used can be settled by the selection of one or more of the available
representations and control structures.  The expert's task is thus to enlarge
{\sl what} it is the program knows.

	There is a corollary assumption in the belief  that the control
structures and representations are comprehensible to the expert (at the
conceptual level), so  that he can express his knowledge with them.  This is
required to insure that the expert understands system performance well enough to
know what to correct and to assure that he knows how to express the required
knowledge.  What the expert sees and wants to change is the external behavior of
the system.  Mapping  from the desired (external) behavior to the necessary
internal modification is often quite subtle and requires an intimate
understanding of the system structure.  Part of the ``art of debugging'' is an
understanding of this mapping.  We are thus assuming that the representation of
knowledge and the manner in which knowledge is used will be sufficiently
comprehensible to the expert that he can understand program behavior
in these {\index{ production rules}}terms.\ffnote{In terms of a performance program that uses a rule-based
representation of knowledge, for instance, this means, more specifically,
that we assume the expert is familiar with the fundamental structure,
organization, and use of production rules.  He need only understand them at
the conceptual level, since part of establishing the link between expert
and program involves insulating him from details of implementation.  The
central issue is that they share a common language of knowledge expression
and use.}

	It follows, from these two assumptions, 
that the  performance programs should {\index{ knowledge base}}have
the architecture suggested in Figure 1--2.  The {\sl knowledge
base} is the program's store of task-specific knowledge that makes
possible high performance.  The {\sl inference engine} is an interpreter that
{\index{ inference engine}}uses the knowledge base to solve the problem at hand.

% .STARTFIG; BOXFIG;CENTER
% ⊂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂⊃
% }   ⊂∂∂∂∂∂∂∂∂∂∂∂⊃   }
% }   } INFERENCE }   }
% }   }  ENGINE   }   }
% }   α%∂∂∂∂∂∂∂∂∂∂∂$   }
% }   ⊂∂∂∂∂∂∂∂∂∂∂∂⊃   }
% }   } KNOWLEDGE }   }
% }   }   BASE    }   }
% }   α%∂∂∂∂∂∂∂∂∂∂∂$   }
% α%∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂$
% 
% .FIG(The architecture of the performance program,PPARCH:);
% .ENDFIG;|

\vskip 10pc
\figtitle 1-2{The architecture of the performance program.}
\noindent
The main point here is the explicit
division between these two parts of the program.  This design is in keeping with
the assumption noted above that the expert's task would be to augment the
knowledge base of a program whose control structure (inference engine) is 
assumed both appropriate and debugged.  If all of the control structure
information is kept in the inference engine, then we can engage the domain
expert in a discussion of the knowledge base and be assured that the discussion
will deal only with issues of domain-specific expertise (rather than
with questions of programming and control structures).  If all of the domain-specific
knowledge is kept in the knowledge base then the program should have a degree
of domain independence, that is, it should be possible to ``unplug'' one knowledge
{\index{ domain independence}}base and ``plug in'' another.

	This division is also in keeping with the aim of accumulating large
amounts of knowledge.  Experience in constructing large, task-oriented systems
[Feigenbaum 71] suggests that this separation makes augmentation of program
performance a far easier task than  would be the case if the distinction were not maintained.

	Given this general architecture, we can picture the situation in 
Figure 1--1 in more detail, viewing {\TEIRESIAS} as a means of establishing a link
between the domain expert and the performance program, Figure 1--3.

% .STARTFIG; BOXFIG;
% 
%        ⊂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂⊃
%        }           TEIRESIAS                                  }
%        }                          ⊂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂⊃   }
% E      }                          }  PERFORMANCE PROGRAM  }   }
%        }    ⊂∂∂∂∂∂∂∂∂∂∂∂∂∂⊃       }    ⊂∂∂∂∂∂∂∂∂∂∂∂⊃      }   }
% X    <===== } EXPLANATION } <=====}==  } INFERENCE }      }   }
%        }    }             }       }    }  ENGINE   }      }   }
% P      }    α%∂∂∂∂∂∂∂∂∂∂∂∂∂$       }    α%∂∂∂∂∂∂∂∂∂∂∂$      }   }
%        }                          }    ⊂∂∂∂∂∂∂∂∂∂∂∂⊃      }   }
% E      }    ⊂∂∂∂∂∂∂∂∂∂∂∂∂∂⊃       }    } KNOWLEDGE }      }   }
%      =====@ } KNOWLEDGE   } ======}=@  }   BASE    }      }   }
% R      }    } ACQUISITION }       }    α%∂∂∂∂∂∂∂∂∂∂∂$      }   }
%        }    α%∂∂∂∂∂∂∂∂∂∂∂∂∂$       }                       }   }
% T      }                          α%∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂$   }
%        }                                                      }
%        α%∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂$
% 
% .FIG(``The expert, %6TEIRESIAS%*, and the performance program'', OVERLAY:);
% .ENDFIG;|

\vskip 16pc
\figtitle 1-3{The expert, {\TEIRESIAS}, and the performance program.}

	Given the range of detailed tasks associated with knowledge base
construction, it is not always easy to put the expert in direct contact with the
program {\sl and} keep the dialog comprehensible.  In response, we have devoted
extensive efforts to making the interaction as ``high level'' as possible.  To the
extent that it is feasible, for instance, questions from the system are phrased
in terms of the manipulation of objects in the domain and not as manipulations of
program structures.  This helps ``insulate'' the expert from implementation-level
details (see especially chapters 6 and 7).

	Our success with this problem has been varied.  Viewed in terms of who might be
able to use {\TEIRESIAS}, there are operations that could be performed
by someone who had
only the briefest introduction to the system; others require more
extensive experience; still others presume some programming experience; and
some require interactions comprehensible only to the program's author.
There are far more of the first sort and reassuringly few of the last.  Those
that remain low level are invariably tasks that are both conceptually
difficult and unfamiliar to nonprogrammers (\eg, designing a data structure
for a new representation).

\sectionskip
\sectionbegin[3]{Scope of the Problem}
	Chapters 3 through 7 deal with four problems
encountered in attempting to reach the pair of goals outlined above.
Each of these problems supplied a major topic of
investigation and was considered individually in broadly applicable terms.
Each is characterized below by a description of the problem and an indication of
an acceptable solution.  The chapters that follow describe the attempts to solve
these problems and explore the extent to which an acceptable level of
performance has been achieved.
\index{ explanation}

	Chapter 3 discusses efforts to enable the performance program to
explain its actions.  The fundamental goal was to design a facility that
would allow the program to explain itself to a wide-ranging audience that
might include: an expert who wanted to debug its knowledge base, a user who
requested its services, and a student with minimal experience in the field
who wanted to learn from it.
\index{ knowledge acquisition}

	Chapter 4 provides a brief overview of our perspective on knowledge
acquisition, while
chapter 5 describes techniques that make it possible for the expert\index{ inference rules}
to supply new inference rules, using a restricted subset of the language and
vocabulary natural to the domain.  It illustrates the utility of setting
knowledge acquisition in the context of shortcomings in the knowledge base and
{\index{ expectations}}describes how the program forms expectations
during its interaction with the
expert.  The basic goal here was to make the knowledge transfer process
both easy enough
and ``intelligent'' enough so that the expert alone could make significant additions
to the knowledge base.

	Chapter 6 discusses the acquisition of new conceptual primitives. 
{\index{ knowledge base management}}This chapter
views the process in terms of a knowledge base and data structure management
task and describes the techniques developed for effective performance when data
structures and representations are uncomplicated.  More generally, it explores
the use of meta-level knowledge as a tool for knowledge base management.  The
goal here was to make it possible for the expert to build an entire knowledge
base from scratch.

	Finally, chapter 7 examines the problem of representation and use of
{\index{ strategies}}strate\-gies that enable a program to make more efficient
use of its knowledge
base.  It also explores the larger question of meta-level knowledge as a
framework for the organization and expression of strategies and examines issues
of implementation and efficiency.

\sectionskip
\sectionbegin[4]{Method}
	The central theme of this work is the exploration and use of what
{\index{ meta-level knowledge}}we have labeled {\sl meta-level knowledge}.  This concept
takes several different
forms as its use is explored, but can be summed up as ``knowing what you
know.'' It makes possible a system with both the capacity to use its
knowledge directly and the ability to examine it, abstract it, and direct
its application.

	To see how this might be done, recall that one of the principal
problems of AI is the question of representation and use of knowledge about
the world.  Much progress has been made and numerous techniques have been
developed.  One way to view what we have done is to imagine turning this
idea of knowledge representation in on itself, using some of these same
techniques to describe parts of the program itself.  Thus we have a program
containing both object-level representations describing the external world
and meta-level representations describing the internal world of
representations.

	In the general context of building a large knowledge base,
meta-level know\-ledge has been used as a tool for the management of
object-level knowledge.  We report on the capabilities made possible by
this approach and document cases where its absence has resulted in
significant difficulties.  Chapter 3 describes the explanation system,
which involves giving the performance program a model of its control
structures and an ``understanding'' of its representations; chapter 5
documents the use of abstracted models of knowledge as a guide to
acquisition; chapter 6 demonstrates the utility of describing to the system
the structure of its knowledge base; and chapter 7 describes the use of
strategies that contain knowledge about the use of knowledge.

	Keep in mind that meta-level knowledge does not refer to a single
entity but is used as a generic term for several different kinds of
information.  Each of these chapters explores one or more manifestations of
it.

\sectionskip
\sectionbegin[5]{Range of Application}
	We noted above that it is the expert's task to enlarge what it is
the program knows, working within the existing set of representations and
control structures to correct shortcomings he finds in the knowledge 
base.  Within this framework we can imagine a range of different shortcomings that
he might uncover:

\listbegin
\hddlistentry[Ignorance]{Some piece of knowledge is missing.}
\hddlistentry[Stupidity]{Some piece of knowledge is incorrect.}
\hddlistentry[Incompetence]{The current set of conceptual primitives is
incapable of expressing a needed piece of knowledge.}
\hddlistentry[Formalism bug]{The control structure has a bug, or the set
of available representations is inadequate.}
\listend

From these we can get a feeling for the range of application of the
techniques described in subsequent chapters.  We will be concerned here
with the first three (although there is an important class of
incompetence-type errors that cannot be handled; see chapter 6) and will
make no
attempt to deal with the last.  This means that the tools provided are
capable of making extensive changes to the knowledge base but none at all
to the basic control structures.

	Since the expert is constrained to work with the available set of
representations and control structures, our approach is also limited to
dealing with knowledge in the application domain that can be formalized and
expressed within the range of available techniques.  This is a substantial
assumption, since knowledge in some domains is ill-specified and it is
unclear what even the basic conceptual primitives should be.  In other
domains, processes may be so well understood that definitive algorithms can
be specified, eliminating the need to accumulate large amounts of informal
knowledge.

	Our approach to knowledge acquisition is geared to domains whose
level of formalization falls somewhere between these two extremes.  The
``vocabulary'' of conceptual primitives should be established, but knowledge
should still be incomplete enough that problem solving is a heuristic
process.  The knowledge should also be decomposable into small, modular
``chunks'' that can be expressed with a simple syntax.  The latter implies
that both the number of interacting factors and the complexity of their
interaction are limited.  For a range of tasks, knowledge expressed in
{\index{ production rules}}production rules meets both constraints.

\sectionskip
\sectionbegin[6]{A Word about natural language}
	Natural language has not been a major focus of this work; for
the most part, we have used the simplest techniques that would support the level of
performance required.  
All questions and responses from {\TEIRESIAS} are either pre-formed or based on a
simple template completion mechanism (as evidenced by the appearance of phrases
like ``a area'').  Responses from the user are of three general types:
single-token answers to multiple choice questions, strings belonging to a
synthetic language with a formal grammar, and heavily stylized natural language
sentences using a restricted vocabulary (examples of all of these are seen
in subsequent chapters).  The first is handled in the obvious way, the second relies on a simple
parser that matches user input against a BNF specification of valid responses,
and the last relies on straightforward keyword analysis. 

	This approach has served thus
far to keep the interaction acceptably ``natur\-al,'' without unreasonable
processing overhead.  It
appears to be viable where unrestricted dialog is not the
goal and for domains where there is available a semiformal technical language
with a low degree of ambiguity.  Since, in our experience, technical interchange
in such domains is often ungrammatical (relying instead on technical terms to
convey meaning), a heavily grammar-based approach might not have fared well in
any case.

\sectionskip
\sectionbegin[7]{Themes}
	There are at least two different, completely orthogonal
organizations of the ideas presented here.  The first is suggested by the
table of contents, which indicates chapters dealing with four basic tasks:

\listbegin
\numlistentry[1]{Explanation.}
\numlistentry[2]{Acquisition of new inference rules.}
\numlistentry[3]{Acquisition of new conceptual primitives.}
\numlistentry[4]{Encoding, organization, and use of strategies.}
\listend

\noindent
All of these employ techniques based on different varieties of meta-level
knowledge.

	The second organization of the material is suggested by the
collection of catch-phrases below.  These represent themes that recur
throughout the remainder of this work.  It will be useful to keep these
in mind as an alternative set of issues addressed by the work.  They will
be revisited in the final chapter to see how close {\TEIRESIAS} has  come to some of
the ideals they imply.  They are purposely oversimplified here for the sake
of clarity and are intended only to be suggestive, conveying by keywords
and phrases some of the character of the work that follows.

\listbegin
\numlistentry[1]{Task-specific high-level languages make code easier to read.}
\numlistentry[2]{Knowledge in programs should be explicit and accessible.}
\numlistentry[3]{Programs can be self-understanding.}
\numlistentry[4]{Programs can have access to and an understanding of their own representations.}
\numlistentry[5]{Programs can have some grasp of their own complexity.}
\numlistentry[6]{Programs can be self-adjusting.}
\numlistentry[7]{Representations can usefully be more than a densely encoded
string of bits.}
\listend

\worldend